//#pragma once
//#ifndef UNIONFINDSET_H
//#define UNIONFINDSET_H
//
//#include <vector>
//
///*
// *	@brief:	初始化并查集
// *	@param:	数组-存放全部节点
// *	@param:	数组的大小
//*/
//inline void init_ufs(int* p, int size) {
//	// 负数表示根节点
//	// p[i]的绝对值表示集合元素的个数
//	for (int i = 0; i < size; ++i) {
//		p[i] = -1;
//	}
//}
//
///*
// *	@brief:	查找当前节点所在集合的根节点
// *	@param:	数组-存放全部节点
// *	@param:	当前节点
// *	@return:当前节点所在集合的根节点
//*/
//inline int Find(int* p, int v) {
//	if (p[v] < 0)return v;				// 返回根节点
//	else return p[v] = Find(p, p[v]);	// 递归查找根节点，同时压缩路径
//}
///*
// *	@brief:	合并不同节点所在集合的根节点
// *	@param:	数组-存放全部节点
// *	@param:	集合1节点
// *	@param:	集合2节点
//*/
//inline void Union(int* p, int v1, int v2) {
//	// 查找两个节点的所在集合的根节点
//	int rootV1 = Find(p, v1);
//	int rootV2 = Find(p, v2);
//	// 判断两个节点，若不是在同一个集合
//	if (rootV1 != rootV2) {
//		// 节点数少的集合，合并到节点数多的集合
//		// v2 少于 v1
//		if (p[rootV1] < p[rootV2]) {
//			p[rootV1] += p[rootV2];		// 更新合并后的节点数
//			p[rootV2] = rootV1;
//		}
//		// 两个集合，节点数相同 or v1 少于 v2
//		else {
//			p[rootV2] += p[rootV1];
//			p[rootV1] = rootV2;
//		}
//	}
//}
//#endif // !UNIONFINDSET_H

#pragma once
#ifndef UNIONFINDSET_H
#define UNIONFINDSET_H

#include <vector>

/*
 *	@brief:	初始化并查集
 *	@param:	数组-存放全部节点
 *	@param:	数组的大小
*/
inline void init_ufs(int* p, int size) {
	// 负数表示根节点
	// p[i]的绝对值表示集合元素的个数
	for (int i = 0; i < size; ++i) {
		p[i] = -1;
	}
}

/*
 *	@brief:	查找当前节点所在集合的根节点（循环实现）
 *	@param:	数组-存放全部节点
 *	@param:	当前节点
 *	@return:当前节点所在集合的根节点
*/
inline int Find(int* p, int v) {
	int root = v;

	// 循环查找根节点
	while (p[root] >= 0) {
		root = p[root];
	}

	// 路径压缩：将从v到root路径上的所有节点直接连接到root
	int temp = v;
	while (temp != root) {
		int parent = p[temp];
		p[temp] = root;  // 直接连接到根节点
		temp = parent;
	}

	return root;
}

/*
 *	@brief:	合并不同节点所在集合的根节点
 *	@param:	数组-存放全部节点
 *	@param:	集合1节点
 *	@param:	集合2节点
*/
inline void Union(int* p, int v1, int v2) {
	// 查找两个节点的所在集合的根节点
	int rootV1 = Find(p, v1);
	int rootV2 = Find(p, v2);

	// 判断两个节点，若不是在同一个集合
	if (rootV1 != rootV2) {
		// 节点数少的集合，合并到节点数多的集合
		// 注意：p[root]存储的是负的元素个数
		if (p[rootV1] < p[rootV2]) {  // rootV1的元素更多
			p[rootV1] += p[rootV2];    // 更新合并后的节点数
			p[rootV2] = rootV1;
		}
		else {  // rootV2的元素更多或相等
			p[rootV2] += p[rootV1];
			p[rootV1] = rootV2;
		}
	}
}

#endif // !UNIONFINDSET_H